home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / unicharutil / nsCompressedCharMap.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  15KB  |  375 lines
  1. /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is Mozilla Communicator client code.
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Netscape Communications Corporation.
  19.  * Portions created by the Initial Developer are Copyright (C) 2001
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *   Brian Stell <bstell@netscape.com>
  24.  *
  25.  * Alternatively, the contents of this file may be used under the terms of
  26.  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27.  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28.  * in which case the provisions of the GPL or the LGPL are applicable instead
  29.  * of those above. If you wish to allow use of your version of this file only
  30.  * under the terms of either the GPL or the LGPL, and not to allow others to
  31.  * use your version of this file under the terms of the MPL, indicate your
  32.  * decision by deleting the provisions above and replace them with the notice
  33.  * and other provisions required by the GPL or the LGPL. If you do not delete
  34.  * the provisions above, a recipient may use your version of this file under
  35.  * the terms of any one of the MPL, the GPL or the LGPL.
  36.  *
  37.  * ***** END LICENSE BLOCK ***** */
  38.  
  39. #ifndef NSCOMPRESSEDCHARMAP_H
  40. #define NSCOMPRESSEDCHARMAP_H
  41. #include "prtypes.h"
  42. #include "nsICharRepresentable.h"
  43.  
  44. #define ALU_SIZE PR_BITS_PER_LONG
  45. //#define ALU_SIZE 16
  46. //#define ALU_SIZE 32
  47. //#define ALU_SIZE 64
  48. #if (ALU_SIZE==32)
  49. #   define ALU_TYPE                PRUint32
  50. #   define CCMAP_POW2(n)           (1L<<(n))
  51. #   define CCMAP_BITS_PER_ALU_LOG2 5
  52. #elif (ALU_SIZE==64)
  53. #   define ALU_TYPE                PRUint64
  54. #   define CCMAP_POW2(n)           (1L<<(n))
  55. #   define CCMAP_BITS_PER_ALU_LOG2 6
  56. #else
  57. #   define ALU_TYPE                PRUint16
  58. #   define CCMAP_POW2(n)           (1<<(n))
  59. #   define CCMAP_BITS_PER_ALU_LOG2 4
  60. #endif
  61.  
  62.  
  63. class nsICharRepresentable;
  64.  
  65. extern PRUint16* CreateEmptyCCMap();
  66. extern PRUint16* MapToCCMap(PRUint32* aMap);
  67. extern PRUint16* MapperToCCMap(nsICharRepresentable *aMapper);
  68. extern void FreeCCMap(PRUint16* &aMap);
  69. extern PRBool NextNonEmptyCCMapPage(const PRUint16 *, PRUint32 *);
  70. extern PRBool IsSameCCMap(PRUint16* ccmap1, PRUint16* ccmap2);
  71. #ifdef DEBUG
  72. void printCCMap(PRUint16* aCCMap);
  73. #endif
  74.  
  75.  
  76. // surrogate support extension
  77. extern PRUint16*
  78. MapToCCMapExt(PRUint32* aBmpPlaneMap, PRUint32** aOtherPlaneMaps, PRUint32 aOtherPlaneNum);
  79.  
  80. // 
  81. // nsCompressedCharMap
  82. // 
  83. // A Compressed Char Map (CCMap) saves memory by folding all
  84. // the empty portions of the map on top of each other.
  85. //
  86. // Building a Compressed Char Map (CCMap) is more complex than
  87. // accessing it.  We use the nsCompressedCharMap object to 
  88. // build the CCMap. Once nsCompressedCharMap has built the CCMap
  89. // we get a copy of the CCMap and discard the nsCompressedCharMap 
  90. // object.  The CCMap is an array of PRUint16 and is accessed by 
  91. // a macro.
  92. //
  93. // See "Character Map Compression" below for a discussion of
  94. // what the array looks like.
  95.  
  96. //
  97. // The maximum size a CCMap:
  98. //  (16 upper pointers) + (16 empty mid pointers) +
  99. //  (16 empty page)     + (16*16 max mid pointers) +
  100. //  (256*16 max pages)  =  4400 PRUint16
  101. #define CCMAP_MAX_LEN (16+16+16+256+4096)
  102.  
  103. // non-bmp unicode support extension
  104. #define EXTENDED_UNICODE_PLANES    16
  105.  
  106. class nsCompressedCharMap {
  107. public:
  108.   nsCompressedCharMap();
  109.   ~nsCompressedCharMap();
  110.  
  111.   PRUint16* NewCCMap();
  112.   PRUint16* FillCCMap(PRUint16* aCCMap);
  113.   PRUint16  GetSize() {return mUsedLen;};
  114.   void      SetChar(PRUint32);
  115.   void      SetChars(PRUint16*);
  116.   void      SetChars(PRUint16, ALU_TYPE*);
  117.   void      SetChars(PRUint32*);
  118.   void      Extend() {mExtended = PR_TRUE;} // enable surrogate area
  119.  
  120. protected:
  121.   union {
  122.     PRUint16 mCCMap[CCMAP_MAX_LEN];
  123.     ALU_TYPE used_for_align; // do not use; only here to cause
  124.                              // alignment
  125.   } u;
  126.   PRUint16 mUsedLen;   // in PRUint16
  127.   PRUint16 mAllOnesPage;
  128.  
  129.   PRBool mExtended;
  130.  
  131.   // for surrogate support
  132.   PRUint32* mExtMap[EXTENDED_UNICODE_PLANES+1];
  133.   PRUint32  mMap[UCS2_MAP_LEN];
  134. };
  135.  
  136. //
  137. // Character Map Compression
  138. //
  139. // Each font requires its own 8k charmap.  On a system with 200 
  140. // fonts this would take: 200 * 8K = 1600K memory.
  141. //
  142. // Since most char maps are mostly empty a significant amount
  143. // of memory can be saved by not allocating the unused sections.
  144. //
  145. // If the map has one or more levels of indirection then the
  146. // the empty sections of the map can all be folded to a single
  147. // common empty element. In this way only the non-empty sections 
  148. // need space. Because the empty sections actually point to a
  149. // common empty section every entry in the map can be valid
  150. // without requiring actually allocating space. 
  151. // Some larger CJK fonts have large sections where every bit
  152. // is set.  In the same way that the empty sections are folded
  153. // onto one "empty page", the sections where all bits are set are 
  154. // folded on to one "all bits set page" .
  155. //
  156. // Break up the Unicode range bits 0x0000 - 0xFFFF
  157. // into 3 bit ranges:
  158. //
  159. // upper bits: bit15 - bit12
  160. //   mid bits: bit11 -  bit8
  161. //  page bits:  bit7 -  bit0
  162. //
  163. // within a page, (assumming a 4 byte ALU)
  164. //    bits 7-5 select one of the 8 longs
  165. //    bits 4-0 select one of the 32 bits within the long
  166. //
  167. // There is exactly one upper "pointers" array.
  168. //
  169. // The upper pointers each point to a mid array.  If there are no chars 
  170. // in an upper pointer's block that pointer points to the empty mid.
  171. // Thus all upper pointers are "valid" even if they do not have space
  172. // allocated; eg: the accessor macro does not need to test if the 
  173. // pointer is zero.
  174. //
  175. // Each mid pointer in the mid array points to a page. If there are no
  176. // chars in a mid pointer's page that pointer points to the empty page.
  177. // Thus all mid pointers are "valid" even if they do not have space
  178. // allocated; eg: the accessor macro does not need to test if the 
  179. // pointer is zero.
  180. //
  181. // Since the array will be less than 5K PRUint16 the "pointers" can
  182. // be implemented as 2 byte offsets from the base instead of
  183. // real pointers.
  184. //
  185. // the format of the CCMap is
  186. //     the upper pointers     (16 PRUint16)
  187. //     the empty mid pointers (16 PRUint16)
  188. //     the empty page         (16 PRUint16)
  189. //     non-empty mid pointers and pages as needed
  190.  
  191. // One minor note: for a completely empty map it is actually 
  192. // possible to fold the upper, empty mid, and empty page
  193. // on top of each other and make a map of only 32 bytes.
  194. #define CCMAP_EMPTY_SIZE_PER_INT16    16
  195.  
  196. // offsets to the empty mid and empty page
  197. #define CCMAP_EMPTY_MID  CCMAP_NUM_UPPER_POINTERS
  198. #define CCMAP_EMPTY_PAGE CCMAP_EMPTY_MID+CCMAP_NUM_MID_POINTERS
  199.  
  200. // 
  201. // Because the table is offset based the code can build the table in a
  202. // temp space (max table size on the stack) and then do one alloc of 
  203. // the actual needed size and simply copy over the data.
  204. //
  205.  
  206. //
  207. // Compressed Char map surrogate extension 
  208. //
  209. // The design goal of surrogate support extension is to keep efficiency 
  210. // and compatibility of existing compressed charmap operations. Most of 
  211. // existing operation are untouched. For BMP support, very little memory 
  212. // overhead (4 bytes) is added. Runtime efficiency of BMP support is 
  213. // unchanged. 
  214. //
  215. // structure of extended charmap:
  216. //    ccmap flag      1 PRUint16 (PRUint32) , indicates if this is extended or not
  217. //    bmp ccmap size  1 PRUint16 (PRUint32) , the size of BMP ccmap, 
  218. //    BMP ccmap       size varies, 
  219. //    plane index     16 PRUint32, use to index ccmap for non-BMP plane
  220. //    empty ccmap     16 PRUint16, a total empty ccmap
  221. //    non-BMP ccmaps  size varies, other non-empty, non-BMP ccmap
  222. //   
  223. // Changes to basic ccmap 
  224. //  2 PRUint16 (PRUint32 on 64bit machines) are added in the very beginning. 
  225. // One is used to specify the size 
  226. // of the ccmap, the other is used as a flag. But these 2 fields are indexed 
  227. // negatively so that all other operation remain unchanged to keep efficiency. 
  228. // ccmap memory allocation is moved from nsCompressedCharMap::NewCCMap to 
  229. // MapToCCMap.
  230. //
  231. // Extended ccmap 
  232. //  A 16*PRUint32 array was put at the end of basic ccmap, each PRUint32 either 
  233. // pointed to the empty ccmap or a independent plane ccmap. Directly after this 
  234. // array is a empty ccmap. All planes that has no character will share this ccmap. 
  235. // All non-empty plane will have a ccmap. 
  236. //  "MapToCCMapExt" is added to created an extended ccmap, each plane ccmap is 
  237. // created the same as basic one, but without 2 additional fields.
  238. //  "HasGlyphExt" is used to access extended ccmap, it first need to locate the 
  239. // plane ccmap, and then operated the same way as "HasGlyph". 
  240. //
  241. // Compatibility between old and new one
  242. // Because extended ccmap include an exactly identical basic ccmap in its head, 
  243. // basic ccmap operation (HasGlyph) can be applied on extended ccmap without 
  244. // problem. 
  245. // Because basic ccmap is now have a flag to indicate if it is a extended one, 
  246. // Extended ccmap operation (HasGlyphExt) can check the flag before it does 
  247. // extended ccmap specific operation. So HasGlyphExt can be applied to basic ccmap 
  248. // too.  
  249. //
  250.  
  251. // Page bits
  252. //
  253. #define CCMAP_BITS_PER_PAGE_LOG2    8
  254. #define CCMAP_BITS_PER_PAGE         CCMAP_POW2(CCMAP_BITS_PER_PAGE_LOG2)
  255. #define CCMAP_BIT_INDEX(c)          ((c) & PR_BITMASK(CCMAP_BITS_PER_ALU_LOG2))
  256. #define CCMAP_ALU_INDEX(c)          (((c)>>CCMAP_BITS_PER_ALU_LOG2) \
  257.                & PR_BITMASK(CCMAP_BITS_PER_PAGE_LOG2 - CCMAP_BITS_PER_ALU_LOG2))
  258.  
  259. #define CCMAP_PAGE_MASK             PR_BITMASK(CCMAP_BITS_PER_PAGE_LOG2)
  260. #define CCMAP_NUM_PRUINT16S_PER_PAGE \
  261.                          (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_PRUINT16)
  262. // one bit per char
  263. #define CCMAP_NUM_ALUS_PER_PAGE     (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_ALU)
  264. #define CCMAP_NUM_UCHARS_PER_PAGE   CCMAP_BITS_PER_PAGE
  265.  
  266. //
  267. // Mid bits
  268. //
  269. #define CCMAP_BITS_PER_MID_LOG2     4
  270. #define CCMAP_MID_INDEX(c)          \
  271.       (((c)>>CCMAP_BITS_PER_PAGE_LOG2) & PR_BITMASK(CCMAP_BITS_PER_MID_LOG2))
  272. #define CCMAP_NUM_MID_POINTERS    CCMAP_POW2(CCMAP_BITS_PER_MID_LOG2)
  273. #define CCMAP_NUM_UCHARS_PER_MID    \
  274.                CCMAP_POW2(CCMAP_BITS_PER_MID_LOG2+CCMAP_BITS_PER_PAGE_LOG2)
  275.  
  276. //
  277. // Upper bits
  278. //
  279. #define CCMAP_BITS_PER_UPPER_LOG2   4
  280. #define CCMAP_UPPER_INDEX(c)        \
  281.       (((c)>>(CCMAP_BITS_PER_MID_LOG2+CCMAP_BITS_PER_PAGE_LOG2)) \
  282.          & PR_BITMASK(CCMAP_BITS_PER_UPPER_LOG2))
  283. #define CCMAP_NUM_UPPER_POINTERS    CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2)
  284.  
  285. //
  286. // Misc
  287. //
  288. #define CCMAP_BITS_PER_PRUINT16_LOG2 4
  289. #define CCMAP_BITS_PER_PRUINT32_LOG2 5
  290.  
  291. #define CCMAP_BITS_PER_PRUINT16 CCMAP_POW2(CCMAP_BITS_PER_PRUINT16_LOG2)
  292. #define CCMAP_BITS_PER_PRUINT32 CCMAP_POW2(CCMAP_BITS_PER_PRUINT32_LOG2)
  293. #define CCMAP_BITS_PER_ALU      CCMAP_POW2(CCMAP_BITS_PER_ALU_LOG2)
  294.  
  295. #define CCMAP_ALUS_PER_PRUINT32  (CCMAP_BITS_PER_PRUINT32/CCMAP_BITS_PER_ALU)
  296. #define CCMAP_PRUINT32S_PER_ALU  (CCMAP_BITS_PER_ALU/CCMAP_BITS_PER_PRUINT32)
  297. #define CCMAP_PRUINT32S_PER_PAGE (CCMAP_BITS_PER_PAGE/CCMAP_BITS_PER_PRUINT32)
  298.  
  299. #define CCMAP_ALU_MASK       PR_BITMASK(CCMAP_BITS_PER_ALU_LOG2)
  300. #define CCMAP_ALUS_PER_PAGE  CCMAP_POW2(CCMAP_BITS_PER_PAGE_LOG2 \
  301.                                        - CCMAP_BITS_PER_ALU_LOG2)
  302. #define NUM_UNICODE_CHARS    CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2 \
  303.                                        +CCMAP_BITS_PER_MID_LOG2 \
  304.                                        +CCMAP_BITS_PER_PAGE_LOG2)
  305. #define CCMAP_TOTAL_PAGES    CCMAP_POW2(CCMAP_BITS_PER_UPPER_LOG2 \
  306.                                        +CCMAP_BITS_PER_MID_LOG2)
  307.  
  308. #define CCMAP_BEGIN_AT_START_OF_MAP 0xFFFFFFFF
  309.  
  310. //
  311. // Finally, build up the macro to test the bit for a given char
  312. //
  313.  
  314. // offset from base to mid array
  315. #define CCMAP_TO_MID(m,c) ((m)[CCMAP_UPPER_INDEX(c)])
  316.  
  317. // offset from base to page
  318. #define CCMAP_TO_PAGE(m,c) ((m)[CCMAP_TO_MID((m),(c)) + CCMAP_MID_INDEX(c)])
  319.  
  320. // offset from base to alu
  321. #define CCMAP_TO_ALU(m,c) \
  322.           (*((ALU_TYPE*)(&((m)[CCMAP_TO_PAGE((m),(c))])) + CCMAP_ALU_INDEX(c)))
  323.  
  324. // test the bit
  325. #define CCMAP_HAS_CHAR(m,c) (((CCMAP_TO_ALU(m,c))>>CCMAP_BIT_INDEX(c)) & 1)
  326.  
  327. // unset the bit
  328. #define CCMAP_UNSET_CHAR(m,c) (CCMAP_TO_ALU(m,c) &= ~(CCMAP_POW2(CCMAP_BIT_INDEX(c))))
  329.  
  330. #define CCMAP_SIZE(m) (*((m)-1))
  331. #define CCMAP_FLAG(m) (*((m)-2))
  332. #define CCMAP_EXTRA    (sizeof(ALU_TYPE)/sizeof(PRUint16)>2? sizeof(ALU_TYPE)/sizeof(PRUint16): 2)
  333. #define CCMAP_SURROGATE_FLAG         0x0001  
  334. #define CCMAP_NONE_FLAG              0x0000
  335.  
  336. // get plane number from ccmap, bmp excluded, so plane 1's number is 0.
  337. #define CCMAP_PLANE_FROM_SURROGATE(h)  ((((PRUint16)(h) - (PRUint16)0xd800) >> 6) + 1)
  338.  
  339. // same as above, but get plane number from a ucs4 char
  340. #define CCMAP_PLANE(u)  ((((PRUint32)(u))>>16))
  341.  
  342. // scalar value inside the plane
  343. #define CCMAP_INPLANE_OFFSET(h, l) (((((PRUint16)(h) - (PRUint16)0xd800) & 0x3f) << 10) + ((PRUint16)(l) - (PRUint16)0xdc00))
  344.  
  345. // get ccmap for that plane
  346. #define CCMAP_FOR_PLANE_EXT(m, i)  ((m) + ((PRUint32*)((m) + CCMAP_SIZE(m)))[(i)-1])
  347.  
  348. // test the bit for surrogate pair
  349. #define CCMAP_HAS_CHAR_EXT2(m, h, l)  (CCMAP_FLAG(m) & CCMAP_SURROGATE_FLAG && \
  350.                                       CCMAP_HAS_CHAR(CCMAP_FOR_PLANE_EXT((m), CCMAP_PLANE_FROM_SURROGATE(h)), CCMAP_INPLANE_OFFSET(h, l)))
  351. // test the bit for a character in UCS4
  352. #define CCMAP_HAS_CHAR_EXT(m, ucs4)  (((ucs4)&0xffff0000) ?  \
  353.                                       (CCMAP_FLAG(m) & CCMAP_SURROGATE_FLAG) && CCMAP_HAS_CHAR(CCMAP_FOR_PLANE_EXT((m), CCMAP_PLANE(ucs4)), (ucs4) & 0xffff) : \
  354.                                       CCMAP_HAS_CHAR(m, (PRUnichar)(ucs4)) )
  355.  
  356. // macros to ensure that the array defining a pre-compiled CCMap starts
  357. // at an ALU_TYPE boundary instead of just a PRUint16 boundary.
  358. // When invoking the macro, 'typequal' should be either 'const' 
  359. // or empty (NULL). see bug 224337.
  360.      
  361. #define DEFINE_ANY_CCMAP(var, extra, typequal)              \
  362. static typequal union {                                     \
  363.   PRUint16 array[var ## _SIZE];                             \
  364.   ALU_TYPE align;                                           \
  365. } var ## Union =                                            \
  366. {                                                           \
  367.   { var ## _INITIALIZER }                                   \
  368. };                                                          \
  369. static typequal PRUint16* var = var ## Union.array + extra
  370.  
  371. #define DEFINE_CCMAP(var, typequal)   DEFINE_ANY_CCMAP(var, 0, typequal)
  372. #define DEFINE_X_CCMAP(var, typequal) DEFINE_ANY_CCMAP(var, CCMAP_EXTRA, typequal)
  373.  
  374. #endif // NSCOMPRESSEDCHARMAP_H 
  375.